5章 レプリケーション

レプリケーションとは

ネットワークで接続された複数のマシンに同じデータのコピーを保持しておくこと

データベースのコピーを保持するノードはレプリカと呼ばれる。データベースへの書き込みは全てレプリカで処理されなければならない。

レプリケーションの目的

高可用性

ネットワーク障害時の操作

レイテンシ

スケーラビリティ

レプリケーションの課題

結果整合性

並行性

利用できなくなったノード

ネットワーク障害

レプリケーションへのアプローチ

シングルリーダーレプリケーション

メリット

わかりやすい

衝突解決を気にしなくて良い

デメリット

リーダーとユーザー間が単一障害点になる

マルチリーダーレプリケーション

メリット

信頼性向上

パフォーマンス

オフライン時

デメリット

衝突解決

リーダーレスレプリケーション

どのレプリカも直接クライアントからの書き込みを受け付けられるようにするかコーディネータノードがクライアントの代わりに送信を行うものがある。

AmazonのDynamoシステムからDynamoスタイルとも呼ぶ

メリット

信頼性向上

デメリット

並行性

レプリケーションのラグに対する一貫性モデル

read-after-write一貫性

ユーザーがページを読み込み直した時に、自分で投入した更新が必ず反映されていることを保証すること。（他のユーザーについては保証しない）

実現方法

ユーザーが変更したかもしれないものの読み取りはリーダーから行い、それ以外はフォロワーから読み取る

ユーザーがアプリケーションの持つ情報をほとんど編集可能な場合

例えば最後の更新を追跡して最新の更新から一分以内の読み取りはリーダーから行う。

あるいはフォロワーのレプリケーションラグを監視して一分以上リーダーから遅延しているフォロワーに対してクエリを行わない。

複数のデータセンターに配置されている場合は、リーダーが返答しなければならないリクエストはリーダーを含むデータセンターにまでルーティングする必要がある。

モノトニックな読み取り

ユーザーが複数のレプリカから複数回読み取りを行う場合に、過去に遡って情報がユーザーに見えないことを保証すること。

実現方法

レプリカをユーザーIDのハッシュ値に基づいて決める

レプリカに障害が起きたら別のレプリカにルーティングする必要がある

一貫性のあるプレフィックス読み取り

ある順序で一連の書き込みが行われた場合、それらの書き込みを読み取るものには必ず書き込まれた際と同じ順序でそれらが見える

実現方法

互いに因果関係を持つ書き込みが同じパーティションにかかれるようにする

ただし、アプリケーションによってはこれを効率的に実現できない（「事前発生」の関係と並行性にて）

「事前発生」の関係性と並行性

2つの操作が並行しているかをどう判定するか。

並行での書き込みの検知のためのアルゴリズム

サーバは全てのキーについてバージョン番号を管理し、キーに対して書き込みが行われるたびにバージョン番号 をインクリメントし、書き込まれた値を合わせて新しいバージョン番号を保持する。

クライアントがキーを読み取る際に、サーバは上書きされていない全ての値を最新のバージョン番号と合わせて返す。クライアントはキーに対して書き込みを行う前に、そのキーを読み取らなければならない。

クライアントはキーを書き込む場合、以前の読み取りで得たバージョン番号を含め、その読み取りで得た全ての値をマージしなければならない。

バージョン番号を含む書き込みを受診すると、サーバはそのバージョン番号もしくはそれ以下のバージョン番号を持つ全ての値を上書きできる。ただし、それ以上のバージョン番号を持つ値は、受診した書き込みと並行しているため全て保持したままにしておかなければならない。

並行で書き込まれた値のマージ

並行で書き込まれた値（sibling）をマージしてクリーンアップする

ユーザーが取り除くことを考えた場合、2つのsiblingからあるアイテムが削除されていたらマージ時に墓石(tombstone)と呼ばれる削除マーカーを残す。